#include <set>
#include <list>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;

typedef vector<string> VS;
typedef vector<int> VI;

#define Rep(i,n) for(int i=0;i<(n);i++)
#define For(i, a, b) for(int i=(a);i<=(b);i++)
#define All(a) (a).begin(), (a).end()


struct TNode
{
	typedef TNode *pointer;
	typedef map<char, TNode> Next_Type;

	struct Find_Collector
	{
		string str;
		set<string> collected;
		void collectThis()
		{
			collected.insert(str);
		}
		void push(char c){str.push_back(c);}
		void pop(){str.resize(str.size()-1);}
	};

	bool bEnd;
	Next_Type next;

	TNode()
	{
		bEnd=false;
	}

	void add(const char* p)
	{
		char c=*p++;
		if(c==NULL)
		{
			bEnd=true;
			return;
		}
		next[c].add(p);
	}

	bool find(const char* p) const // mis-match tolerance
	{
		char c=*p++;
		Next_Type::const_iterator it=next.find(c);
		if(next.find(c)==next.end())
			return false;

		const TNode& n=it->second;
		if(*p!=0)
			return n.find(p);
		else
			return n.bEnd;
	}

	bool find(const char* p, int mm_tol, Find_Collector& ctor) const// mis-match tolerance
	{
		if(mm_tol<0)
			return false;

		const char c=*p;
		const char* pn=p+1;

		// we've got the string!
		if(bEnd && c==NULL)
		{
			ctor.collectThis();
			return true;
		}

		bool got=false;

		// for insertion based, we'll ignore this char in source string
		{
			if(c!=NULL && find(pn, mm_tol-1, ctor))
				got=true;
		}

		for(Next_Type::const_iterator it=next.begin();
			it!=next.end();it++)
		{
			ctor.push(it->first);

			const TNode& n=it->second;

			// modification based
			if(c!=NULL)
			{
				int n_mm_tol=mm_tol;
				if(it->first != c)
					n_mm_tol--;

				if(n.find(pn, n_mm_tol, ctor))
					got=true;
			}

			// deletion based, the char is missing in the passed in string, use the original pointer to match next
			{
				if(n.find(p, mm_tol-1, ctor))
					got=true;
			}

			ctor.pop();
		}
		return got;
	}
};

void my_tolower(char& c)
{
	c=(char)tolower(c);
}


int main()
{
	TNode root;

	ifstream in("dic.txt");

	if(!in)
	{
		cout<< "Can't find dic.txt"<<endl;
		return 0;
	}

	cout<< "start construct trie..." <<endl;
	while(in)
	{
		string word;
		in>>word;
		root.add(word.c_str());
	}
	cout<< "construction finished"<<endl;

	string s;
	while(s!="quit")
	{
		TNode::Find_Collector ctor;
		cout<<"=============================="<<endl;
		int tol=s.size()>5 ? s.size()/5 : 1;
		if(root.find(s.c_str(), tol, ctor))
		{
			for(set<string>::iterator it=ctor.collected.begin();
				it!=ctor.collected.end();
				it++)
				cout<< *it <<endl;
		}
		cout<<">>>";
		cin>>s;
	}

	return 0;
}


